#include <iostream>
#include <vector>
#include <algorithm>

using std::vector;
using std::cout;
using std::swap;

int getIdx(vector<int>& v,int targt,int end)
{
    for(int i = 0;i < end;++ i)
    {
        if(targt > v[i] && targt < v[i + 1]) return i + 1;
    }
    return end;
}

void insertSort(vector<int>& v)
{
    for(size_t i = 0;i < v.size() - 1;++ i)
    {

        if(v[i + 1] < v[i])
        {
            // 找到大于v[i + 1],小于v[i + 1]的位置
            int target = v[i + 1];
            int idx = getIdx(v,target,i);
            // idx后所有元素往后挪
            for(int j = i;j >= idx;-- j)
            {
                v[j + 1] = v[j];
            }
            v[idx] = target;
        }
    }
}


void insertSort2(vector<int>& v)
{
    for(size_t i = 0;i < v.size() - 1;++ i)
    {
        if(v[i + 1] < v[i])
        {
            for(int j = i;j >= 0 && v[j] > v[j + 1];-- j)
            {
                swap(v[j],v[j + 1]);
            }
        }
    }
}


int main(int argc, char const *argv[])
{
    vector<int> v({5, 2, 6, 67, 7, 4, 3, 6, 9, 44, 32});
    insertSort2(v);
    
    for (auto &num : v)
    {
        cout << num << " ";
    }
    cout << "\n";
    getchar();
    return 0;
}
